#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    unordered_map<string, int> mp; // string -> id
    vector<vector<int>> edges;     // 邻接表

    void AddWord(string& word) {
        if (!mp.count(word)) {
            mp[word] = mp.size();
            edges.emplace_back();
        }
    }

    void AddVirtualEdge(string& word) {
        int id = mp[word];
        for (int i = 0; i < word.length(); i++) {
            char temp = word[i];
            word[i] = '*';
            AddWord(word);
            edges[mp[word]].emplace_back(id);
            edges[id].emplace_back(mp[word]);
            word[i] = temp;
        }
    }


    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // 建图
        AddWord(beginWord);
        for (int i = 0; i < wordList.size(); i++) {
            AddWord(wordList[i]);
        }
        if (!mp.count(endWord)) {
            return 0;
        }
        AddVirtualEdge(beginWord);
        for (int i = 0; i < wordList.size(); i++) {
            AddVirtualEdge(wordList[i]);
        }

        // 宽搜
        vector<int> dis(mp.size(), INT_MAX);
        int beginId = mp[beginWord], endId = mp[endWord];
        dis[beginId] = 0;

        queue<int> q;
        q.push(beginId);
        while(!q.empty()) {
            int temp = q.front();
            q.pop();

            if (temp == endId) {
                return dis[endId] / 2 + 1;  //有一半虚拟节点的距离
            }
            for (int i = 0; i < edges[temp].size(); i++) {
                if (dis[edges[temp][i]] == INT_MAX) {
                    dis[edges[temp][i]] = dis[temp] + 1;
                    q.push(edges[temp][i]);
                }
            }
        }
        return 0;
    }
};

/**
 * 2023.4.14
*/